The present disclosure generally relates to a radix tree, and more particularly to determining whether a key is stored in a radix tree.
A radix tree is a data structure that is used to store data. A radix tree may be useful for constructing associative arrays with keys that can be expressed as strings and typically supports insertion, deletion, and search operations. The insertion operation adds a new string to the radix tree while trying to minimize the amount of data stored. The deletion operation removes a string from the radix tree. A search operation may include an exact lookup of a string, a lookup of a predecessor or successor of the string, or a lookup of all strings with a particular prefix.